package com.sheng.leetcode.year2022.month08.day13;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author liusheng
 * @date 2022/08/25
 *
 * 768. 最多能完成排序的块 II
 *
 * 这个问题和“最多能完成排序的块”相似，但给定数组中的元素可以重复，输入数组最大长度为2000，其中的元素最大为10**8。
 * arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
 * 我们最多能将数组分成多少块？
 *
 * 示例 1:
 * 输入: arr = [5,4,3,2,1]
 * 输出: 1
 * 解释:
 * 将数组分成2块或者更多块，都无法得到所需的结果。
 * 例如，分成 [5, 4], [3, 2, 1] 的结果是 [4, 5, 1, 2, 3]，这不是有序的数组。
 *
 * 示例 2:
 * 输入: arr = [2,1,3,4,4]
 * 输出: 4
 * 解释:
 * 我们可以把它分成两块，例如 [2, 1], [3, 4, 4]。
 * 然而，分成 [2, 1], [3], [4], [4] 可以得到最多的块数。
 *
 * 注意:
 * arr的长度在[1, 2000]之间。
 * arr[i]的大小在[0, 10**8]之间。
 * 通过次数28,221提交次数48,111
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/max-chunks-to-make-sorted-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0768 {

    @Test
    public void test01() {
//        int[] arr = {5,4,3,2,1};
        int[] arr = {2,1,3,4,4};
        System.out.println(new Solution().maxChunksToSorted(arr));
    }
}
class Solution {
    public int maxChunksToSorted(int[] arr) {
        int length = arr.length;
        //将原数组分割成多块，对每块进行排序后连接起来，和原数组直接排序得到的结果一致
        int[] clone = arr.clone();
        Arrays.sort(clone);
        int index = clone[0];
        //代表分割成的数组的块数
        int count = 0;
        boolean flag = false;
        for (int i = 0; i < length; i++) {
            //如果经过最小值，则可以进行切分数组判断
            if (arr[i] == index) {
                flag = true;
            }
            if (flag) {
                int[] ints = Arrays.copyOf(arr, i + 1);
                Arrays.sort(ints);
                int[] ints1 = Arrays.copyOf(clone, i + 1);
                if (Arrays.equals(ints, ints1)) {
                    if (i != length - 1) {
                        index = clone[i + 1];
                    }
                    count++;
                    flag = false;
                }
            }
        }
        return count;
    }
}

//class Solution {
//    public int maxChunksToSorted(int[] arr) {
//        int[] clone = arr.clone();
//        Arrays.sort(clone);
//        int n = arr.length, ans = 0;
//        Map<Integer, Integer> map = new HashMap<>(16);
//        for (int i = 0, tot = 0; i < n; i++) {
//            int a = arr[i], b = clone[i];
//            // 遍历arr数组，对当前元素a进行判断，是否已经遍历过了
//            if (map.getOrDefault(a, 0) == -1) {
//                // 没遍历过
//                tot--;
//            } else if (map.getOrDefault(a, 0) == 0) {
//                // 遍历过
//                tot++;
//            }
//            map.put(a, map.getOrDefault(a, 0) + 1);
//            // 对排序好的原数组同位置的元素进行操作
//            if (map.getOrDefault(b, 0) == 1) {
//                tot--;
//            } else if (map.getOrDefault(b, 0) == 0) {
//                tot++;
//            }
//            map.put(b, map.getOrDefault(b, 0) - 1);
//            // 当保持一致时，可以进行分割s
//            if (tot == 0) {
//                ans++;
//            }
//        }
//        return ans;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/solution/by-ac_oier-z4wt/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
